/**
 * @param {number[]} strength
 * @return {number}
 */
var totalStrength = function (strength) {
  const sum = [0];
  const mod = 1e9 + 7;
  for (let i = 1; i <= strength.length; i++) {
    sum[i] = sum[i - 1] + strength[i - 1];
  }
  // 使用单调栈求解出左侧第个严格小于该数的元素位置，和右侧第一个严格小于该数的元素的位置
  let stack = [];
  const len = strength.length;
  const right = new Array(len).fill(len);
  for (let i = 0; i < len; i++) {
    while (stack.length && strength[stack[stack.length - 1]] > strength[i]) {
      right[stack[stack.length - 1]] = i;
      stack.pop();
    }
    stack.push(i)
  }
  stack = [];
  const left = new Array(len).fill(-1);
  for (let j = len - 1; j >= 0; j--) {
    while (stack.length && strength[stack[stack.length - 1]] > strength[j]) {
      left[stack[stack.length - 1]] = j;
      stack.pop();
    }
    stack.push(j);
  }
  const mp = new Map()
  // 根据前缀和和left， right数组进行枚举求解
  let ans = BigInt(0);
  for (let k = 0; k < len; k++) {
    // const total = BigInt(sum[right[k]] - sum[left[k] + 1]) * BigInt(strength[k]);
    if(!mp.has(strength[k])) mp.set(strength[k], new Set())
    const now = mp.get(strength[k])
    let csum = 0n
    for (let x = left[k] + 1; x <= k; x++) {
      for (let y = right[k]; y >= k + 1; y--) {
        if(now.has(`${x}-${y}`)) continue
        csum += BigInt(sum[y] - sum[x]) * BigInt(strength[k]) % BigInt(mod)
        now.add(`${x}-${y}`)
      }
    }
    ans += csum
  }
  return ans % BigInt(mod);
};
